我們昨天介紹了樹的基本概念和專有名詞，今天要來看最常見的應用 ---- 二元樹 (Binary tree)

二元樹的概念

二元樹是一種特殊的樹，每個內部節點最多只有兩個分支，通常分支叫「左子樹」或「右子樹」

A 的左子樹是 B，右子樹是 C
B 的左子樹是 D、右子樹是 E
C 沒有子樹

二元樹的種類

Full binary tree

每個節點的子節點只能是 0 個或 2 個

Complete binary tree

各層節點全滿，除了最後一層葉節點 (Leaf node)，最後一層節點從左到右依序填充

Perfect binary tree

每層的節點完全被填滿，葉節點的 Degree 為 0，其餘節點的 Degree 為 2
若樹的高度為 h，則節點總數為2^(h+1) - 1

balanced binary tree

左子樹和右子樹的層級 (Level) 相差不超過 1

節點結構

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x){
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

和鏈結串列的節點很像，只是next變成了left和right兩個指標，分別指向左右節點

走訪方式

樹狀結構不像鏈結串列只有一條路徑可以走，走訪二元樹主要有四種方式，差別在於 什麼時候處理當前節點

前序走訪(Preorder)：

順序 : root → left → right

void preorder(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->val << " ";   // 先處理自己
    preorder(node->left);       // 再走左子樹
    preorder(node->right);      // 最後走右子樹
}

輸出 : A B D E C F

中序走訪(Inorder)：

順序 : left → root → right

void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);        // 先走左子樹
    cout << node->val << " ";   // 再處理自己
    inorder(node->right);       // 最後走右子樹
}

輸出：D B E A C F

後序走訪(Postorder)：

順序 : left → right → root

void postorder(TreeNode* node) {
    if (node == nullptr) return;
    postorder(node->left);      // 先走左子樹
    postorder(node->right);     // 再走右子樹
    cout << node->val << " ";   // 最後處理自己
}

輸出：D E B F C A

完整程式碼

#include <iostream>
using namespace std;

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) {
        val = x;
        left = nullptr;
        right = nullptr;
    }
};

void preorder(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->val << " ";
    preorder(node->left);
    preorder(node->right);
}

void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->val << " ";
    inorder(node->right);
}

void postorder(TreeNode* node) {
    if (node == nullptr) return;
    postorder(node->left);
    postorder(node->right);
    cout << node->val << " ";
}

int main() {
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');
    TreeNode* F = new TreeNode('F');

    A->left = B;
    A->right = C;
    B->left = D;
    B->right = E;
    C->right = F;

    TreeNode* root = A;

    cout << "前序: ";
    preorder(root);
    cout << endl;

    cout << "中序: ";
    inorder(root);
    cout << endl;

    cout << "後序: ";
    postorder(root);
    cout << endl;

    return 0;
}

輸出 :

前序: A B D E C F
中序: D B E A C F
後序: D E B F C A

時間複雜度

參考資料和書籍

1. Hello 算法
2. 資結筆記｜二元樹（Binary Tree）
3. Full Binary Tree
4. binary tree -演算法筆記
5. 二元樹 - CodiMD
6. Binary Tree: Intro(簡介) - Chiu CC
7. Binary 二元樹 -Coding Hot pot